#include <iostream>
#include <vector>
#include <cassert>

using namespace std;

/**
 * 对撞指针(左右两端两个指针向中间对撞)
 * [O(n), O(1)]
 */
class Solution{
	public:
		vector<int> twoSum(vector<int>& numbers, int target){
			int l = 0, r = numbers.size() - 1;
			while(l < r){
				if(numbers[l] + numbers[r] == target){
					int res[2] = {l + 1, r + 1}; // 返回下标 + 1
					return vector<int>(res, res + 2);
				}else if(numbers[l] + numbers[r] < target){
					l ++;
				}else{
					r --;
				}
			}
			throw invalid_argument("the input has no solution");
		}

};
